<template>
  <div></div>
</template>

<script>
  
import md from '@/markdowns/algor-strArrange.md'
  
export default {
  name: 'algor-strArrange',
  components: {
    
  },
  data () {
    return {
      
    }
  },
  watch: {
    
  },
  computed: {
    
  },
  methods: {
    // 字符串的全排列，剪去重复枝
    getStrArranges (str) {
      const len = str.length
      // 保存结果
      let res = []
      // 对原字符串进行排序，确保重复的字符总是相邻，默认是升序
      str = str.split('').sort().join('')
      
      // 递归寻找排列
      const deepSearchArrange = (level, usedArr, currentStr) => {
        if (level === len) {
          // 所有数字已经用完
          res.push(currentStr)
          return
        }
        for (let i = 0; i < len; i++) {
          // 遍历字符串，寻找没有用过的字符，加入当前排列子串，并且继续向深处递归
          if (!usedArr[i]) {
            if (i > 0 && str[i] === str[i - 1] && !usedArr[i - 1]) {
              // 这个判断用于去重，每一种字符只能在同一个位置上出现一次。
              // 因为我们前面对字符串做了排序处理，所以重复字符只可能出现在相邻位置
              continue
            }
            usedArr[i] = true
            deepSearchArrange(level + 1, usedArr, currentStr + str[i])
            // 如果没有使用该字符串，置回false
            usedArr[i] = false
          }
        }
      }
      
      // 第二个参数数组的作用：作为和字符串长度相等的数组，用于记录对应位置的字符是否被使用于排列
      deepSearchArrange(0, new Array(len), '')
      
      return res
    }
  },
  created () {
    
  },
  mounted () {
    this.$el.innerHTML = this.$md(md)
    
    // 字符串的全排列算法
    console.log('abc的全部排列', this.getStrArranges('abc'))
    console.log('abbacb的全部排列(剪枝去重)',this.getStrArranges('abbacb'))
  },
}
  
</script>

<style>
</style>
